|
In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of Turing machine. == Operation == A linear bounded automaton is a nondeterministic Turing machine that satisfies the following three conditions: * Its input alphabet includes two special symbols, serving as left and right endmarkers. * Its transitions may not print other symbols over the endmarkers. * Its transitions may neither move to the left of the left endmarker nor to the right of the right endmarker. In other words: instead of having potentially infinite tape on which to compute, computation is restricted to the portion of the tape containing the input plus the two tape squares holding the endmarkers. An alternative, weaker definition is as follows: * Like a Turing machine, an LBA possesses a tape made up of cells that can contain symbols from a finite alphabet, a head that can read from or write to one cell on the tape at a time and can be moved, and a finite number of states. * An LBA differs from a Turing machine in that while the tape is initially considered to have unbounded length, only a finite contiguous portion of the tape, whose length is a linear function of the length of the initial input, can be accessed by the read/write head; hence the name ''linear bounded automaton''.〔 This limitation makes an LBA a somewhat more accurate model of a real-world computer than a Turing machine, whose definition assumes unlimited tape. The strong and the weaker definition lead to the same computational abilities of the respective automaton classes,〔 due to the ''linear speedup theorem''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Linear bounded automaton」の詳細全文を読む スポンサード リンク
|